package main.leetcode.clockin.Auguest;

import main.datastruc.TreeNode;

import java.util.List;

/**
 * 99. 恢复二叉搜索树
 *
 * <p>二叉搜索树中的两个节点被错误地交换。
 *
 * <p>请在不改变其结构的情况下，恢复这棵树。
 */
public class day8 {
    private TreeNode x, y, pre = new TreeNode(Integer.MIN_VALUE);

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        new day8().recoverTree(root);
        System.out.println(root);
    }

    /** 中序递归 */
    public void recoverTree(TreeNode root) {
        dfs(root);
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);

        // 写法1，pre无需初始化
        //        if (pre != null && pre.val > root.val) {
        //            y = root;
        //            if (x == null) {
        //                x = pre;
        //            } else {
        //                return;
        //            }
        //        }

        // 写法2，pre需初始化为最小值
        if (x == null && pre.val > root.val) {
            x = pre;
        } else if (x != null) {
            y = root;
        }

        pre = root;
        dfs(root.right);
    }

    //    /** 中序迭代 */
    //    public void recoverTree(TreeNode root) {
    //        if (root == null) {
    //            return;
    //        }
    //        Deque<TreeNode> stack = new LinkedList<>();
    //        TreeNode x = null, y = null, pre = null;
    //        while (!stack.isEmpty() || root != null) {
    //            while (root != null) {
    //                stack.offerLast(root);
    //                root = root.left;
    //            }
    //            if (!stack.isEmpty()) {
    //                root = stack.pollLast();
    //                if (pre != null && root.val < pre.val) {
    //                    y = root;
    //                    if (x == null) {
    //                        x = pre;
    //                    } else {
    //                        break;
    //                    }
    //                }
    //                pre = root;
    //                root = root.right;
    //            }
    //        }
    //        int tmp = x.val;
    //        x.val = y.val;
    //        y.val = tmp;
    //    }

    //	/** 使用数组存储中序遍历的值 */
    //    public void recoverTree(TreeNode root) {
    //        List<Integer> list = new ArrayList<>();
    //        inorder(root, list);
    //        int[] target = find2Nodes(list);
    //        swap2Nodes(root, target, 2);
    //    }

    private void swap2Nodes(TreeNode root, int[] target, int cnt) {
        if (root == null) {
            return;
        }
        int x = target[0], y = target[1];
        if (root.val == x || root.val == y) {
            root.val = root.val == x ? y : x;
            if (--cnt == 0) {
                return;
            }
        }
        swap2Nodes(root.left, target, cnt);
        swap2Nodes(root.right, target, cnt);
    }

    private int[] find2Nodes(List<Integer> list) {
        int x = -1, y = -1;
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i) > list.get(i + 1)) {
                // 因为x、y交换后，相应位置的数一个变大了，一个变小了
                y = list.get(i + 1);
                if (x == -1) {
                    x = list.get(i);
                } else {
                    break;
                }
            }
        }
        return new int[] {x, y};
    }

    private void inorder(TreeNode root, List<Integer> list) {
        if (root != null) {
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }
}
